#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <iomanip>

#include "GameTree.h"
#include "common_func.h"
#include "HashTable.h"

using namespace std;

extern char MoveTab[32][5];
extern char OrderTab[34][34];

/* GameTreeNode */

GameTreeNode::GameTreeNode(char d, move m, char* b, char* p, bool side)  // Constructor
{    
    _depth = d;
    _path = m;
    _round = side;
    
    for (char i=0 ; i<32 ; i++)
    {
        _board[i] = b[i];
        _piece[i] = p[i];
    }
    stop_check();
}

void GameTreeNode::GenerateLegalMoves()
{
    int begin;
    if (_round == 0)
    {
        begin = 0;       
    }
    else    
    {
        begin = 16;
    }
    
    for(int i = begin ; i < begin + 16 ; i++)
    {
        if(_piece[i] != -1 && _piece[i] != -2)
        {
            for (int j = 0 ; j < 4 ; j++)
            {
                //cout << "Piece " << i << " Board " << _piece[i] ;
                //cout << " MoveTab" << "[" << _piece[i] << "][" << j+1 << "] : " << _MoveTab[_piece[i]][j+1] ;
                //cout << " OrderTab " << "[" << i+1 << "][" << _board[_MoveTab[_piece[i]][j+1]] << "] : "  << OrderTab[i+1][_board[_MoveTab[_piece[i]][j+1]]] << endl;
                if (MoveTab[_piece[i]][j+1] != -1 && OrderTab[i+1][_board[MoveTab[_piece[i]][j+1]]] == 0)
                {
                    if (_stop == 0)
                    {
                        if ((_depth > 0) || (_depth <= 0 && _board[MoveTab[_piece[i]][j+1]] != 0))
                            {
                            move legalMove(_piece[i],MoveTab[_piece[i]][j+1]);
                            char new_board[32];
                            char new_piece[32];
                            for (int k = 0 ; k < 32 ; k++)
                            {
                                new_board[k] = _board[k];
                                new_piece[k] = _piece[k];
                            }
                            if (_board[MoveTab[_piece[i]][j+1]] != 0 && _board[MoveTab[_piece[i]][j+1]] != 33)
                            {
                                new_piece[_board[MoveTab[_piece[i]][j+1]]-1] = -1;       
                                new_piece[i] = MoveTab[_piece[i]][j+1];               
                            }
                            if (_board[MoveTab[_piece[i]][j+1]] == 0)
                            {
                                new_piece[i] = MoveTab[_piece[i]][j+1];    
                            }
                            new_board[MoveTab[_piece[i]][j+1]] = _board[_piece[i]];
                            new_board[_piece[i]] = 0;    
                            GameTreeNode* newChild = new GameTreeNode(_depth - 1, legalMove, new_board, new_piece, (_round+1)%2);
                            _child.push_back(newChild);
                            //cout << "from " << legalMove._from << " to " << legalMove._to << endl;
                        }
                    }
                }
            }         
        }        
    }
    
    return ;
}

void GameTreeNode::stop_check()
{
    if (Win())
    {
        _stop = true;
        return;      
    }
    if(_depth <= 0)
    {
        if (CapMove() == 0)
        {
            _stop = true;
            return;
        }   
    }
    _stop = false;
}

bool GameTreeNode::Win()
{
     int black_num = 0;
     int red_num = 0;
     for (int i = 0 ; i < 16 ; i++)
     {
         if (_piece[i] != -1)
         {
             black_num++;
         }
         if (_piece[i+16] != -1)
         {
             red_num++;
         }
     }
     if (black_num == 0 && _round == 1)
     {
         return true ;         
     }
     if (red_num == 0 && _round == 0)
     {
         return true;        
     }
     return false;
}

int GameTreeNode::CapMove()
{
    int cap_num = 0;
    for (int i = 0 ; i < 32 ; i++)
    {
        if(_board[i] >= 1 && _board[i] <= 32)
        {
            if((_board[i]-1)/16 == _round)
            {
                for (int j = 0 ; j < 4 ; j++)
                {
                    if( (MoveTab[i][j+1] != -1) && (OrderTab[_board[i]][_board[MoveTab[i][j+1]]] == 0) )
                    {
                        if (_board[MoveTab[i][j+1]] != 0)
                        {
                            cap_num++;
                        }
                    }
                }
            }
        }
    }
    //cout << "Oh Oh  cap_num = " << cap_num << endl;

    return cap_num;        

}

/* GameTree */

GameTree::GameTree(char* b, char* p, char h, bool side){
    _height = h;
    move rootMove(32,32);
    _root = new GameTreeNode(h - 1, rootMove, b, p, side);
    //createTree();
}
/*
void GameTree::createTree(){
    growTree(_root, 0);
}

void GameTree::growTree(GameTreeNode* node, int stopDepth){
    if (node->_depth == stopDepth) return;
    //static int count = 1;
    //move legalMove;
    node->GenerateLegalMoves();
    
    while(node->GenerateLegalMoves(legalMove)){
        GameTreeNode* newChild = new GameTreeNode(node->_depth - 1, count, legalMove, 
                                                  node->_board, node->_piece);
        node->_child.push_back(newChild);
        count++;
    }
    vector<GameTreeNode*>::iterator it;
    int c=0;
    for (it=(node->_child).begin() ; it<(node->_child).end() ; it++){
        growTree(*it, stopDepth);
    }
}
*/
void GameTree::destroyTree()  //to be modified!!!
{
	destroySubtree(_root);
}

void GameTree::destroySubtree(GameTreeNode* node)
{
	unsigned int i;
	if(!(node->_child.empty())) //if node has children...
	{
		for(i = 0; i < node->_child.size() ; i++)
		{
			destroySubtree(node->_child.at(i));
		}
	}
	else
		delete node;
}

GameTreeNode* GameTree::cutChild(int i)   //cut the i-th child
{
	GameTreeNode* temp;
	temp = _root->_child.at(i);
	return temp;
}

void GameTree::printTree(){
    ofstream fout;
    fout.open("out.txt");
    if (!fout.is_open()) cout << "Open fail !";
    fout << "digraph GameTree {\n";
    printTreeRe(_root, fout, 0);
    fout << "}";
    fout.close();
    
    system("\"c:\\Program Files\\Graphviz 2.21\\bin\\twopi.exe\" -Tgif out.txt -o out.gif");
    system("out.gif");
    
}

void GameTree::printTreeRe(GameTreeNode* node, ofstream& fout, int parent_order){
    if (node->_depth == 0) return;
    static int order = 0;
    vector<GameTreeNode*>::iterator it;
    for (it=(node->_child).begin() ; it<(node->_child).end() ; it++){
        fout << "  \"" << node->_depth << "-" << parent_order << "\"" << " -> "
             << "\"" << (*it)->_depth << "-" << ++order << "\"" << "\n";
        printTreeRe(*it, fout, order);
    }
}

void GameTree::printTreeJS(){
    ofstream fout;
    fout.open("printTree\\body.txt");
    if (!fout.is_open()) cout << "Open fail !";
    printTreeReJS(_root, fout);
    system("copy /Y printTree\\header.txt+printTree\\body.txt+printTree\\footer.txt printTree\\test.htm");
    system("printTree\\test.htm");
}

void GameTree::printTreeReJS(GameTreeNode* node, ofstream& fout){
    if (node->_depth == 0) return;
    static int order = 0;
    static int count = 0;
    vector<GameTreeNode*>::iterator it;
    if (order == 0)
        fout << "<ul id=\"list_" << order << "\">";
    else{
        fout << "<ul id=\"list_" << order << "\" class=\"child " << ((node->_depth)%2 ? "first" : "second") << "\">";
    }
    for (it=(node->_child).begin() ; it<(node->_child).end() ; it++){
        fout << "<li>";
        if ((*it)->_child.size()!=0) 
            fout << "<span onclick=\"menu('list_" << ++order << "')\">" << (int)(*it)->_depth << " - " << ++count << "</span>";
        else
            fout << (int)(*it)->_depth << " - " << ++count << " - leaf";
        printTreeReJS(*it, fout);
        fout << "</li>\n";
    }
    fout << "</ul>";
}


void GameTree::printMove(GameTreeNode* node){
        if (node->_depth==0)
         return ;
        cout << "Depth: " << node->_depth << " Side: " << node->_round << "--\n";
        cout << "FROM: " << node->_path._from << " TO: " << node->_path._to <<" over" <<endl;
        
        //cout<<"score is "<<endl;
        //cout << "child size : " << node->_child.size() << endl;
        vector<GameTreeNode*>::iterator it;
        for (it=(node->_child).begin() ; it<(node->_child).end() ; it++){
            printMove(*it);
        }

}

int GameTree::AlphaBeta(GameTreeNode* node , char d, int alpha , int beta , GameTreeNode* &kid){
    
    int val;
    int foundPV = 0;
    //cout<<node->ProbeHash(alpha,beta)<<" fuck! "<<endl;
    if(node->ProbeHash(alpha,beta)!=valUNKNOWN)
        {return node->ProbeHash(alpha,beta);}

    if(node->_stop){
        //cout<<"the node value is : "<<node->utility()<<endl;
        if(node->_round==0)
            return node->utility()-_root->utility();
        else
            return -(node->utility()-_root->utility());
    }

//    if(node->_child.empty()){
//        //cout<<"the node value is : "<<node->utility()<<endl;
//        if(node->_round==0)
//        return node->utility()-_root->utility();
//        else
//        return -(node->utility()-_root->utility());
//        }    

      if(node->ProbeHash(alpha,beta)!=valUNKNOWN)
          {return node->ProbeHash(alpha,beta);  }
        
    node->GenerateLegalMoves();
    for(vector<GameTreeNode*>::iterator it = node->_child.begin();it != node->_child.end();it++) {
        val=-AlphaBeta((*it),node->_depth-1,-beta,-alpha,kid);
        if(val>=beta){
            if(val==beta && ((*it)->_depth==_root->_depth-1))
                kid = (*it);
            node->RecordHash(beta,BETA_FLAG);
            return beta;
            }
          

        if(val>alpha){
            alpha=val;
            foundPV=1;
            if((*it)->_depth==_root->_depth-1)
                kid = (*it);
            }

        }
    
    if(foundPV) 
        node->RecordHash(alpha,PV_FLAG);
    else
        node->RecordHash(alpha,ALPHA_FLAG);
    return alpha;
    }
    
int GameTreeNode::utility(){  
    _score=0;
    evaluation();//initializing and adjusting the truely valuation
    
    for (int i =0;i<32;i++){
        if(_piece[i]==-1) //compute only when we have lost the chess.
        _score+=_pieceScore[i];
        }
    return _score;
    }
    
void GameTreeNode::evaluation(){
    //initial
    _pieceScore[0]=-810;_pieceScore[16]=810;
    
    for(int i =1;i<3;i++){
        _pieceScore[i]=-270;
        _pieceScore[i+16]=270;
        }
    for(int i =3;i<5;i++){
        _pieceScore[i]=-90;
        _pieceScore[i+16]=90;
        }
    for(int i =5;i<7;i++){
        _pieceScore[i]=-18;
        _pieceScore[i+16]=18;
        }    
    for(int i =7;i<9;i++){
        _pieceScore[i]=-6;
        _pieceScore[i+16]=6;
        }
    for(int i =9;i<11;i++){
        _pieceScore[i]=-18;
        _pieceScore[i+16]=18;
        }
    for(int i =11;i<16;i++){
        _pieceScore[i]=-1;
        _pieceScore[i+16]=1;
        }
                                
    // adjusting
    //if(_piece[0]==-2){
        //_pieceScore[9]=_pieceScore[10]=_pieceScore[1];
        
        //for(int i =11;i<16;i++)
            //_pieceScore[i]=_pieceScore[3];
        //}
    //if(_piece[16]==-2){
       // _pieceScore[27]=_pieceScore[10]=_pieceScore[1];
        
        //for(int i =11;i<16;i++)
       //     _pieceScore[i]=_pieceScore[3];
       // }    
}

void GameTreeNode::RecordHash(int val, int hashf)
{
    for(int i =0;i<32;i++)
    {
    if(_board[i]!=0)
        ZobristKey^=Zobrist[_board[i]][i];
    ZobristKey^=_round;
    }
     HashNode *p = &Hash_Table[ZobristKey&(TABLE_SIZE - 1)];
     if(_depth >= p->depth)
     {
 
          //if(ZobristKey%43==1)
//cout<<ZobristKey<<"fuck you"<<endl;
          p->key = ZobristKey;
          p->depth = _depth;
          p->hashf = hashf;
     }
}

int GameTreeNode::ProbeHash(int alpha,int beta)
{   
    for(int i =0;i<32;i++)
          {
             //ZobristKey^=Zobrist[i][_piece[i]];

             if(_board[i]!=0)
             {
              ZobristKey^=Zobrist[_board[i]][i];
              ZobristKey^=_round;
             }
          }
    HashNode *p = &Hash_Table[ZobristKey&(TABLE_SIZE - 1)];
    if(ZobristKey == p->key && p->depth >= _depth)
    {    
        if(p->hashf==PV_FLAG)
            return p->val;

        if(p->hashf==BETA_FLAG&&p->val>=beta)
            return beta;

        if(p->hashf==ALPHA_FLAG&&p->val<=alpha)
            return alpha;
    }
    return valUNKNOWN;   //failure
}
